"""
3301. 高度互不相同的最大塔高和
中等
相关标签
相关企业
提示
给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。

你的任务是给每一座塔分别设置一个高度，使得：

第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。
所有塔的高度互不相同。
请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -1 。



示例 1：

输入：maximumHeight = [2,3,4,3]

输出：10

解释：

我们可以将塔的高度设置为：[1, 2, 4, 3] 。

示例 2：

输入：maximumHeight = [15,10]

输出：25

解释：

我们可以将塔的高度设置为：[15, 10] 。

示例 3：

输入：maximumHeight = [2,2,1]

输出：-1

解释：

无法设置塔的高度为正整数且高度互不相同。



提示：

1 <= maximumHeight.length <= 105
1 <= maximumHeight[i] <= 109
"""


class Solution(object):
    def maximumTotalSum(self, maximumHeight):
        """
        :type maximumHeight: List[int]
        :rtype: int
        """
        maximumHeight.sort(reverse=True)
        n = len(maximumHeight)
        if n == 1:
            return maximumHeight[0]
        ans = maximumHeight[0]
        for i in range(1, n):
            #如果取的数比左边还大，则当改为：左边高度-1
            if maximumHeight[i]>=maximumHeight[i-1]:
                maximumHeight[i] = maximumHeight[i-1] - 1
                #高度为0，说明不可以满足提议
                if maximumHeight[i]<=0:
                    return -1
                #修改当前的实际高度，用于下次循环判断
                ans += maximumHeight[i]
            else:
                #正常
                ans += maximumHeight[i]
        return ans

if __name__ == '__main__':
    s = Solution()
    print(s.maximumTotalSum([2,2,1]))